import java.util.*;

class TreeNode {
      int val;
      TreeNode left;
      TreeNode right;
      TreeNode() {}
      TreeNode(int val) { this.val = val; }
      TreeNode(int val, TreeNode left, TreeNode right) {
         this.val = val;
          this.left = left;
          this.right = right;
      }
  }

  public class Solution {
    /*给你二叉树的根节点 root ，返回其节点值的 锯齿形层序遍历 。
    （即先从左往右，再从右往左进行下一层遍历，以此类推，层与层之间交替进行）。*/
    public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
        List<List<Integer>> result = new ArrayList<>();
        if(root==null) return result;
        //链表实现队列
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        boolean reverse = false; // 控制是否需要反转

        while (!queue.isEmpty()) {
            int size = queue.size();
            List<Integer> level = new ArrayList<>();

            for (int i = 0; i < size; i++) {
                TreeNode node = queue.poll();
                level.add(node.val);

                if (node.left != null) {
                    queue.offer(node.left);
                }

                if (node.right != null) {
                    queue.offer(node.right);
                }
            }

            if (reverse) {
                Collections.reverse(level);
            }

            result.add(level);
            reverse = !reverse;
        }

        return result;
    }
    /*
    * 给你一棵以root为根的二叉树，请你返回任意二叉搜索子树的最大键值和。
      二叉搜索树的定义如下：

    任意节点的左子树中的键值都小于此节点的键值。
    任意节点的右子树中的键值都大于此节点的键值。
    任意节点的左子树和右子树都是二叉搜索树。
    * */
    private class Result {
        boolean isBST;
        int minVal;
        int maxVal;
        int sum;

        Result(boolean isBST, int minVal, int maxVal, int sum) {
            this.isBST = isBST;
            this.minVal = minVal;
            this.maxVal = maxVal;
            this.sum = sum;
        }
    }
    private int maxSum;

      public int maxSumBST(TreeNode root) {
          maxSum = 0;
          isBST(root);
          return maxSum;
      }

      private Result isBST(TreeNode node) {
          if (node == null) {
              // 空节点视为有效的 BST
              return new Result(true, Integer.MAX_VALUE, Integer.MIN_VALUE, 0);
          }

          Result left = isBST(node.left);
          Result right = isBST(node.right);

          // 判断当前节点是否满足 BST 的条件
          boolean isBST = left.isBST && right.isBST && node.val > left.maxVal && node.val < right.minVal;

          // 计算当前节点对应的 BST 的最小值和最大值
          int minVal = Math.min(node.val, left.minVal);
          int maxVal = Math.max(node.val, right.maxVal);

          // 计算当前节点对应的 BST 的键值和
          int sum = left.sum + right.sum + node.val;

          if (isBST) {
              maxSum = Math.max(maxSum, sum);
          }

          return new Result(isBST, minVal, maxVal, sum);
      }


}
